package cn.zifangsky.linkedlist.questions.nowcoder;

import org.junit.Test;

class ListNode {
    int val;
    ListNode next;
	
    public ListNode(int val) {
		this.val = val;
		this.next = null;
	}

}

/**
 * 使用归并排序链表
 */
public class Problem_001_SortLinkedList {
	
	/**
	 * 归并排序
	 * @时间复杂度 O(nlogn)
	 * @param headNode
	 * @return
	 */
	public ListNode sortList(ListNode head) {
		if(head == null || head.next == null){
			return head;
		}
		
		ListNode slow = head,fast = head;
		//找出中间节点，即：最终的slow节点
		while(fast != null && fast.next != null && fast.next.next != null){
			slow = slow.next;
			fast = fast.next.next;
		}
		
		ListNode halfHeadNode = slow.next;
		slow.next = null;
		
		return mergeNoRecursion(sortList(head), sortList(halfHeadNode));
    }

	/**
	 * 合并两个有序链表
	 * @时间复杂度 O(n/2) = O(n)
	 * @param headNode
	 * @return
	 */
	private ListNode merge(ListNode headNode1,ListNode headNode2){
		ListNode result = null;
		
		if(headNode1 == null) return headNode2;
		if(headNode2 == null) return headNode1;
		
		if(headNode1.val <= headNode2.val){
			result = headNode1;
			result.next = merge(headNode1.next,headNode2);
		}else{
			result = headNode2;
			result.next = merge(headNode1,headNode2.next);
		}
		return result;
	}
	
	/**
	 * 非递归合并两个有序链表
	 * @param headNode1
	 * @param headNode2
	 * @return
	 */
	private ListNode mergeNoRecursion(ListNode headNode1,ListNode headNode2){
		ListNode result, currentNode;
		result = new ListNode(-1);
	    currentNode = result;
	    while (headNode1 != null && headNode2 != null) {
	        if (headNode1.val <= headNode2.val) {
	        	currentNode.next = headNode1;
	            headNode1 = headNode1.next;
	        } else {
	        	currentNode.next = headNode2;
	            headNode2 = headNode2.next;
	        }
	        currentNode = currentNode.next;
	    }
	    currentNode.next = (headNode1 == null) ? headNode2 : headNode1;
	    return result.next;
	}

	public void print(ListNode headNode){
		while(headNode != null){
			System.out.print(headNode.val + " ");
			headNode = headNode.next;
		}
		System.out.println();
	}
	
	@Test
	public void testMethods(){
		ListNode headNode = new ListNode(1);		
		ListNode tmpNode1 = new ListNode(3);
		ListNode tmpNode2 = new ListNode(5);
		ListNode tmpNode3 = new ListNode(6);
		ListNode tmpNode4 = new ListNode(4);
		ListNode tmpNode5 = new ListNode(2);
		
		
		headNode.next = tmpNode1;
		tmpNode1.next = tmpNode2;
		tmpNode2.next = tmpNode3;
		tmpNode3.next = tmpNode4;
		tmpNode4.next = tmpNode5;
		
		System.out.println("排序之前：");
		print(headNode);
		
		headNode = sortList(headNode);
		System.out.println("排序之后： ");
		print(headNode);
		
	}
	
}
